#include <stack>

using std::stack;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        while (root != nullptr) {
            stack.push(root);
            root = root->left;
        }
    }

    int next() {
        TreeNode* t = stack.top();
        int ret = t->val;
        stack.pop();
        if (t->right != nullptr) {
            t = t->right;
            while (t != nullptr) {
                stack.push(t);
                t = t->left;
            }
        }
        return ret;
    }

    bool hasNext() {
        return !stack.empty();
    }
private:
    stack<TreeNode*> stack;
};